def error_diffusion(img: list):
	"""
	:param img: the greyscale image array
	:return: halftone image through error diffusion
	"""
	h, w = img.shape
	
	# prepare the generated img
	out_img: list = []
	
	# prepare a same-sized list to store error
	err_list: list = [[0] * w for _ in range(h)]
	
	# check if index is in the list, if so then accumulate
	def valid_then_acc(i, j, val):
		if 0 <= i < h and 0 <= j < w:
			err_list[i][j] += val
	
	# tranverse image
	for i in range(h):
		out_row: list = []
		for j in range(w):
			pix: int = img[i][j]
			error: float = 0
			if pix + err_list[i][j] < 128:
				out_row.append(0)
				# calculate error
				error = pix + err_list[i][j] - 0
			else:
				out_row.append(255)
				# calculate error
				error = pix + err_list[i][j] - 255
				
			# store error
			valid_then_acc(i, j+1, error * 7/16)
			valid_then_acc(i+1, j-1, error * 3/16)
			valid_then_acc(i+1, j, error * 5/16)
			valid_then_acc(i+1, j+1, error * 1/16)
			
		out_img.append(out_row)
	
	# output processed image
	return out_img

